In database systems, the term concurrency control refers to the algorithm used to ensure that the database has sensible semantics, even in the presence of concurrency. Multiversion concurrency-control algorithms store multiple versions of a given piece of data (one per write), so as to enable greater concurrency. Ideally, a distributed database is semantically equivalent to a single-machine database; concurrency control algorithms that guarantee such a semantics are called “externally consistent”. In an externally-consistent, multiversion, distributed database, consistent reads in the past can be done across the entire database without holding locks. Reads and writes in the present, such as those within read-write transactions, use local synchronization between reads and writes at each object in the database; strict 2-phase locking, along with commit wait (where a transaction delays commit until the timestamp of the transaction is in the past) guarantee external consistency.
Some distributed databases provide an implementation of a virtual global clock, which increases monotonically and reflects real time. Because there is necessarily observational uncertainty in the clock's value, and because events in a program are not instantaneous, a client cannot read the exact value of the clock at any point in time. Instead, the client may be provided with a function that returns an open interval of time in which the lower bound of the interval is lower than the value of the global clock at the instant when the function finishes executing, and the upper bound of the interval is higher than the value of the global clock at the instant when the function starts executing. The function should guarantee that the interval is non-empty. Because time uncertainty fluctuates over time, the width of the returned time interval fluctuates as well. Commit wait takes the upper bound on such an interval and waits until that time has passed.
Existing solutions perform time-based synchronization while holding user-level locks at servers. That is, while writing an object in the database, the server performs commit wait while holding the implementation-level lock that protects exclusive access to the object being written.